package 中等.动态规划.背包;

/**
 * 给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。
 * 请从 nums 中
 * 找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排
 * 列中出现任意次，但是顺序不同的序列被视作不同的组合。
 * 题目数据保证答案符合 32 位整数范围。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/D0F0SV
 */
public class 排列的数目_offer104 {

    public static void main(String[] args) {

    }

    /**
     * 思路和爬楼梯相似，求的是排列数
     * dp[i] 表示目标整数为 i 的排列数是多少，dp[target] 即为答案
     *
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        // 0 什么都不选，一种方案
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

}
